#include <iostream>
#include <vector>
using namespace std;

int SimapleArray[]={27,17,3,16,13,10,1,5,7,12,4,8,9,0};

class PrintInt
{
public:
	void operator()(int elem) const 
	{
		cout << elem<<' ';
	}
};
//MAX-HEAPIFY by recursion
//i from one
void max_heapify_recursion(vector<int> &vec,int i)
{
	int l=2*i;
	int r=2*i+1;
	int largest;
	if(l<=vec.size()&&(vec[l-1]>vec[i-1]))
		largest=l;
	else {
		largest=i;
	}
	if((r<=vec.size())&&(vec[r-1]>vec[largest-1]))
		largest=r;
	if(largest!=i)
	{
		swap(vec[i-1],vec[largest-1]);
		max_heapify_recursion(vec,largest);
	}

}
//MAX-HEAPIFY without recursion
//i from one
void max_heapify_nonrecursion(vector<int> &vec,int i)
{
	int l,r,largest;
	bool Conti=true;
	for(;Conti;i=largest)
	{
		l=2*i,r=2*i+1;
		if(l<=vec.size()&&vec[l-1]>vec[i-1])
			largest=l;
		else 
		{
			largest=i;
		}
		if(r<=vec.size()&&vec[r-1]>vec[largest-1])
			largest=r;
		if(largest!=i)
		{
			swap(vec[i-1],vec[largest-1]);
			Conti=true;
		}
		else
		{
			Conti=false;
			
		}
	}
}



//MIN-HEAPIFY by recursion
//i from one
void min_heapify_recursion(vector<int> &vec,int i)
{
	int l=2*i;
	int r=2*i+1;
	int smallest;
	if(l<=vec.size()&&(vec[l-1]<vec[i-1]))
		smallest=l;
	else {
		smallest=i;
	}
	if((r<=vec.size())&&(vec[r-1]<vec[smallest-1]))
		smallest=r;
	if(smallest!=i)
	{
		swap(vec[i-1],vec[smallest-1]);
		min_heapify_recursion(vec,smallest);
	}
	
}

int main (int argc, char * const argv[]) {
    // insert code here...
	vector<int> A;
	int size=sizeof(SimapleArray)/sizeof(int);
	for(int i=0;i<size;i++)
	{
		A.push_back(SimapleArray[i]);
	}
    cout << "Array before sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	cout<<endl;
	max_heapify_nonrecursion(A,3);
	cout << "Array afert sorting\n";
	for_each(A.begin(), A.end(), PrintInt());
	
	cout<<endl;
	
    return 0;
}
